#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define maxsize 100 // 假设迷宫的最大尺寸
#define M 5 // 迷宫的行数
#define N 5 // 迷宫的列数

typedef struct {
    int i, j;
    int pre; // 用于记录路径的前一个节点在队列中的位置
} Box;

typedef struct {
    Box data[maxsize];
    int front, rear;
} Que;

void InitQue(Que *q) {
    q->front = q->rear = 0;
}

bool QueueEmpty(Que *q) {
    return q->front == q->rear;
}

bool AddQue(Que *q, Box box) {
    if ((q->rear + 1) % maxsize == q->front) { // 队列满
        return false;
    }
    q->data[q->rear] = box;
    q->rear = (q->rear + 1) % maxsize;
    return true;
}

bool DeleteQue(Que *q, Box *box) {
    if (QueueEmpty(q)) {
        return false;
    }
    *box = q->data[q->front];
    q->front = (q->front + 1) % maxsize;
    return true;
}

void PrintPath(Que *q, Box box) {
    int path[maxsize][2], k = 0;
    while (box.pre != -1) { // -1 表示没有前一个节点
        path[k][0] = box.i;
        path[k][1] = box.j;
        box = q->data[box.pre]; // 获取前一个节点
        k++;
    }
    // 反转路径
    for (int i = k - 1; i >= 0; i--) {
        printf("(%d, %d) ", path[i][0], path[i][1]);
    }
}

bool mgPath(Que *q, int xi, int yi, int xe, int ye, int mg[M][N]) {
    Box temp, box;
    int di[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // 上下左右四个方向
    int i, j, find = 0;
    InitQue(q);
    box.i = xi;
    box.j = yi;
    box.pre = -1;
    AddQue(q, box);
    while (!QueueEmpty(q) && !find) {
        DeleteQue(q, &temp);
        for (i = 0; i < 4; i++) {
            int x = temp.i + di[i][0];
            int y = temp.j + di[i][1];
            if (x >= 0 && x < M && y >= 0 && y < N && mg[x][y] == 0) {
                box.i = x;
                box.j = y;
                box.pre = (q->front - 1 + maxsize) % maxsize; // 记录前一个节点在队列中的位置
                mg[x][y] = -1; // 标记为已访问
                if (x == xe && y == ye) { // 找到出口
                    find = 1;
                    AddQue(q, box); // 将出口节点加入队列
                    break;
                }
                AddQue(q, box);
            }
        }
    }
    if (find) {
        // 打印路径,打印起点
        printf("(%d, %d) ",xi,yi);
        PrintPath(q, box);
        return true;
    } else {
        return false;
    }
}

int main() {
    int mg[M][N] = {
        {1, 1, 1, 1, 1},
        {1, 0, 0, 0, 1},
        {1, 0, 1, 0, 1},
        {1, 0, 0, 0, 1},
        {1, 1, 1, 1, 1}
    };
    Que q;
    int sp[2][2]={{1,1},{3,3}};
    if (mgPath(&q, sp[0][0],sp[0][1], sp[1][0], sp[1][1], mg)) {
        printf("Find a path\n");
    } else {
        printf("No path\n");
    }
    return 0;
}
